package leecode

func maximalRectangle(matrix [][]byte) int {
	var res int
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	heights := make([]int, len(matrix[0]))
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == '0' {
				heights[j] = 0
			} else {
				heights[j] += 1
			}
		}
		area := largestRectangleArea85(heights)
		res = max(res, area)
	}
	return res
}

func largestRectangleArea85(heights []int) (result int) {
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	stack := make([]int, 0)
	stack = append(stack, 0)
	for i := 1; i < len(heights); i++ {
		topIndex := stack[len(stack)-1]
		for len(stack) != 0 && heights[i] < heights[topIndex] {
			stack = stack[:len(stack)-1]
			h := heights[topIndex]
			w := i - stack[len(stack)-1] - 1
			result = max(result, h*w)
			topIndex = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	return
}
